/**
 *  @file    DivideLink.c
 *  @brief   按位序奇偶性分解不带头结点的单链表
 *  @details 演示：
 *           1) 创建、尾插法建表
 *           2) 单遍历拆分：奇数位→oddHead，偶数位→evenHead
 *           3) 打印与销毁链
 *           ⚠ 与上一示例不同：本实现**无头结点**，需注意首尾指针处理
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025‑07‑16
 *  @version 1.1
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 节点结构定义 -------------------------

/**
 * @brief 单链表节点
 */
typedef struct node {
    int           data;   ///< 数据域
    struct node  *next;   ///< 指针域
} node, *link;            ///< link 为 node* 类型别名

// ------------------------- 创建节点 -------------------------

/**
 * @brief 申请并初始化一个新节点
 * @param value  节点要存储的整数值
 * @return 成功返回新节点指针；失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return NULL;            // 内存不足
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// ------------------------- 尾插法 -------------------------

/**
 * @brief 尾插法插入新节点
 * @param head   指向链表头指针的指针（可能为空）
 * @param value  要插入的数据
 * @note  复杂度 O(n)，可通过维护尾指针优化
 */
void insertTail(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    if (*head == NULL) {          // 空表：新节点即为表头
        *head = newNode;
        return;
    }

    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 顺序打印链表所有节点
 * @param head  链表头指针
 */
void printList(link head) {
    if (head == NULL) return;

    link cur = head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    puts("");
}

// ------------------------- 销毁链表 -------------------------

/**
 * @brief 释放整条链表
 * @param head  指向链表头指针的指针
 */
void destroyLink(link *head) {
    link cur = *head;
    while (cur != NULL) {
        link next = cur->next;    // 预存后继
        free(cur);                // 释放当前
        cur = next;               // 向前移动
    }
    *head = NULL;                 // 避免悬挂指针
}

// ------------------------- 分解链表 -------------------------

/**
 * @brief 将链表按位序奇偶拆分为 oddHead、evenHead
 * @param head      原链表头指针
 * @param evenHead  偶数位链表头指针输出
 * @param oddHead   奇数位链表头指针输出
 * @complexity 时间 O(n)；空间 O(1)
 */
void divideLink(link head, link *evenHead, link *oddHead) {
    if (head == NULL) return;

    *oddHead  = head;            // 链表首节点为第 1 位 → 奇链首
    link oddTail  = head;        // 奇链尾

    *evenHead = NULL;
    link evenTail = NULL;        // 偶链尾
    link cur      = head->next;  // 从第 2 节点开始扫描
    int  index    = 2;           // 逻辑位序

    while (cur != NULL) {
        link next = cur->next;   // 预存后继
        cur->next = NULL;        // 断开 cur 与原链

        if (index & 1) {         // 奇数位
            oddTail->next = cur;
            oddTail       = cur;
        } else {                 // 偶数位
            if (*evenHead == NULL)
                *evenHead = evenTail = cur;
            else {
                evenTail->next = cur;
                evenTail       = cur;
            }
        }

        cur = next;
        ++index;
    }
    /* 尾端封口，防止脏指针 */
    oddTail->next = NULL;
    if (evenTail) evenTail->next = NULL;
}

// ------------------------- 主函数 -------------------------

/**
 * @brief 功能自测
 */
int main() {
    link head     = NULL;  // 原链表
    link evenHead = NULL;  // 偶数位链表
    link oddHead  = NULL;  // 奇数位链表

    /* 构造链表：1 → 2 → 3 */
    insertTail(&head, 1);
    insertTail(&head, 2);
    insertTail(&head, 3);

    puts("Original list:");
    printList(head);

    /* 拆分 */
    divideLink(head, &evenHead, &oddHead);

    /* 预期输出：
       Odd : 1 3
       Even: 2
    */
    puts("Odd‑index list:");
    printList(oddHead);

    puts("Even‑index list:");
    printList(evenHead);

    /* 释放内存 */
    destroyLink(&oddHead);
    destroyLink(&evenHead);

    return 0;
}
